package com.mengfou.sortextends;

/**
 * 归并排序拓展
 * @author mengfou
 */
public class MergeSortExtend {

    /**
     * 在一个数组中，每一个数左边比当前数小的数累加起来的求和。
     * 更多细节：https://www.kancloud.cn/the_road_of_android/algroithm/2591125
     * @param arr 待计算数组
     * @return 小和
     */
    public int getMinSumByGreedy(int[] arr){
        int len = 0, res = 0;
        if(arr == null || (len = arr.length) == 0) return res;
        for (int i = 0; i < len; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) {
                if(arr[i] > arr[j]){
                    count += arr[j];
                }
            }
            res += count;
        }
        return res;
    }

    /**
     * 在一个数组中，每一个数左边比当前数小的数累加起来的求和。
     * 更多细节：https://www.kancloud.cn/the_road_of_android/algroithm/2591125
     * @param arr 待计算数组
     * @return 小和
     */
    public int getMinSumByMergeSort(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        return twoWayMergeSort(arr, 0, arr.length - 1);
    }

    private int twoWayMergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + ((right - left) >> 1);
            return twoWayMergeSort(arr, left, mid)
                    + twoWayMergeSort(arr, mid + 1, right)
                    + merge(arr, left, mid, right);
        } else return 0;
    }

    private int merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int index = 0;
        int p = low, q = mid + 1;
        int result = 0;
        while (p <= mid && q <= high) {
            if (arr[p] > arr[q]) {
                temp[index++] = arr[q++];
            } else {
                result += arr[p] * (high - q + 1);
                temp[index++] = arr[p++];
            }
        }
        while (p <= mid) {
            temp[index++] = arr[p++];
        }
        while (q <= high) {
            temp[index++] = arr[q++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[low + i] = temp[i];
        }
        return result;
    }
}
